COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00009 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a23.tex[154,phy] \today\hfill}

\bigskip

\noindent {\bf [Subject: Pairing functions, sequences.]}

\def\dddots{\mathinner{\mskip1mu\raise1pt\vbox{\kern7pt\hbox{.}}\mskip2mu
    \raise4pt\hbox{.}\mskip2mu\raise7pt\hbox{.}\mskip1mu}}

\bigskip
$$\vbox{\tabskip=0pt\offinterlineskip
\halign{$\ctr{#}$&$\ctr{#}$\quad&\vrule#&\strut\quad\rt{#}\quad&\rt{#}\quad
&\rt{#}\quad
&\rt{#}\quad
&\rt{#}\quad
&\rt{#}\quad
&\rt{#}\quad
&\rt{#}\cr
&Y\cr
X&&\omit&0&1&2&3&4&5&6&7\cr
&&\multispan9\hrulefill\cr
&&height 2pt\cr
&0&&0&2&5&9&14&20&27\cr
&1&&1&4&8&13&19&26\cr
&2&&3&7&12&18&25\cr
&3&&6&11&17&24\cr
&4&&10&16&23\cr
&5&&15&22&$\dddots$\cr
&6&&21&29\cr
&7&&28\cr}}$$

The above diagram illustrates a pairing function $z=\langle x,y\rangle$
from $N\times N$ to~$N$. The number~$z$ assigned to $\langle x,y\rangle$
is the number of pairs $\langle u,v\rangle$ which precede $\langle x,y\rangle$
in the listing; those are the pairs for which $u+v<x+y$, or
$u+v=x+y$ and $v<y$. Of the latter, there are exactly~$y$. Of the former
there are 
$1+2+3+\cdots +(x+y)={(x+y)(x+y+1)\over 2}$, so
$z=\langle x,y\rangle ={(x+y)(x+y+1)\over 2}+y$. Can we find formulas
for the projection functions $\pi↓1(z)=x$, $\pi↓2(z)=y$?
If we can determine $x+y$ from~$z$, we can subtract ${(x+y)(x+y+1)\over 2}$
from $z$ to get~$y$, and we are done. If we can find a continuous increasing
function $f(z)$ which is truncated to give~$x+y$, $f(z)$~should be equal
to~$x$ when $y=0$; in this case, $z={x(x+1)\over 2}$. Completing the square,
$2z=x↑2+x$, $2z+{1\over 4}=\bigl(x+{1\over 2}\,\bigr)↑2$,
$x+{1\over 2}=\sqrt{2z+1/4}$, or $2x+1=\sqrt{8z+1}$,
$f(z)={\sqrt{8z+1}-1\over 2}$, $x+y=\lfloor f(z)\rfloor$,
$y=z-{(x+y)(x+y+1)\over 2}$, $x=(x+y)-y$.

If $\Sigma$ is a finite set (alphabet) $\{\sigma↓1,\sigma↓2,\ldots,\sigma↓n\}$,
every sequence (string) over $\Sigma$ can be encoded uniquely as a natural
number by $c(\langle\sigma↓{i↓1},\sigma↓{i↓2},\ldots,\sigma↓{i↓m}\rangle)
=\sum↓jn↑j\cdot i↓j$. 

[RWF: define $\pi$]

To allow a numerical coding that uniquely encodes numbers, sequences of
numbers, sequences some of whose elements are themselves sequences, we borrow
a page from LISP. Let $\pi$ be a pairing function from $N\times N$ onto~$N$,
such as the one already defined. Encode the empty sequence~$\langle\,\rangle$ 
as~0, and
each number~$n$ as the odd number $2n+1$. Then encode each non-empty
sequence, recursively, by the non-zero even number
$c(\langle a↓1,a↓2,\ldots, a↓k\rangle)=
2\bigl(\pi\bigl(c(a),{c(\langle a↓2,a↓3,\ldots, a↓k\rangle)\over 2}\bigr)+1\bigr)$.
To decode~$z$:
If $z=0$, $z=c(\langle\,\rangle)$; 
if $z$ odd, $z=c\bigl({z-1\over 2}\bigr)$.
Otherwise, find $a↓1$ such that $\pi↓1(z)=c(a↓1)$, and
$\langle a↓2,a↓3,\ldots,a↓k\rangle$ such that
$2\pi↓2(z)=c(\langle a↓2,a↓3,\ldots,a↓k\rangle)$;
then $z=c(\langle a↓1,a↓2,\ldots, a↓k\rangle)$.

Nobody really uses these unpleasant functions. They serve, though, to
show that ordered pairs, sequences, etc., are not shaky ontologically;
they exist if the natural numbers exist. I~won't argue about whether
the natural numbers exist, except to say that if they don't, then sets
don't exist either. I~believe in the existence of ordered pairs and
triples, sequences, sets, Santa Claus and the tooth fairy. I~am skeptical
about 127-tuples and the Easter bunny, mainly because I~don't care
for what either brings me.

\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft July 20, 1984

\bye